package bTree.LeetCode;

import java.util.ArrayList;
import java.util.List;

public class 括号生成 {
    List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        StringBuilder sb=new StringBuilder();
        backTraking(0,0,sb,n);
        return res;
    }

    private void backTraking(int left, int right, StringBuilder sb, int n) {
        if (left==right&&left==n){
            res.add(new String(sb));
            return;
        }
        if (left<n){
            sb.append('(');
            backTraking(left+1,right,sb,n);
            sb.deleteCharAt(sb.length()-1);
        }
        if (right<n&&right<left){
            sb.append(')');
            backTraking(left,right+1,sb,n);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}